package 算法.leetcode.labuladong.数组和链表;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/6/18
 */
public class 下一个更大的元素I {
    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] ans = new int[nums1.length];
            int[] nums2Greater = getNextGreatNum(nums2);
            Map<Integer,Integer> map = new HashMap<>();
            for (int i=0;i<nums2.length;i++) {
                // nums1[i]对应的nums2[j]后面第一个比它大的元素
                map.put(nums2[i],nums2Greater[i]);
            }

            for (int i=0;i<nums1.length;i++) {
                ans[i] = map.get(nums1[i]);
            }
            return ans;

        }

        int[] getNextGreatNum(int[] nums){
            int[]  ans = new int[nums.length];
            Stack<Integer> stack = new Stack<>();
            for (int i= nums.length-1;i>=0;i--) {
                // 判断高矮个
                while (!stack.isEmpty()&& stack.peek()<=nums[i]){
                    // 矮个让路
                    stack.pop();
                }
                // num[i]后更大的元素
                ans[i] = stack.isEmpty()?-1:stack.peek();
                stack.push(nums[i]);
            }
            return ans;
        }
    }
}
